#define _CRT_SECURE_NO_WARNINGS 1

//https://leetcode.cn/problems/beautiful-arrangement/

class Solution {
    int ret = 0;
    bool check[16] = { false };
public:
    int countArrangement(int n) {
        dfs(n, 1);
        return ret;
    }

    void dfs(int n, int idx)
    {
        if (idx == n + 1)
        {
            ret++;
            return;
        }

        for (int i = 1; i <= n; i++)
        {
            if (check[i] == false && (idx % i == 0 || i % idx == 0))
            {
                check[i] = true;
                dfs(n, idx + 1);
                check[i] = false;
            }
        }
    }
};